package J20250121_Dynamic;

/**
 * Created with IntelliJ IDEA.
 * Description: 动态规划43——46
 * User: 王圆豪
 * Date: 2025-01-26
 * Time: 23:14
 */
public class Solution6 {

    //不同的⼦序列——https://leetcode.cn/problems/distinct-subsequences/
    public int numDistinct(String s, String t) {
        int n = s.length(), m = t.length();
        int[][] dp = new int[m+1][n+1];
        for(int j = 0; j <= n; j++) dp[0][j] = 1;
        for(int i = 1; i <= m; i++){
            for(int j = 1; j <= n; j++){
                dp[i][j] = dp[i][j-1];
                if(s.charAt(j-1) == t.charAt(i-1)) dp[i][j] += dp[i-1][j-1];
            }
        }
        return dp[m][n];
    }
    //通配符匹配——https://leetcode.cn/problems/wildcard-matching/
    public boolean isMatch(String s, String p) {
        // s = s + " ";
        // p = p + " ";
        int m = s.length(), n = p.length();
        char[] ss = s.toCharArray();
        char[] pp = p.toCharArray();
        boolean[][] dp = new boolean[m+1][n+1];
        dp[0][0] = true;
        for(int i = 1; i <= n;i++){
            if(pp[i - 1] == '*') dp[0][i] = true;
            else break;
        }
        for(int i = 1; i <= m; i++){
            for(int j = 1; j <= n; j++){
                if(pp[j-1] == '?' || ss[i-1] == pp[j-1]) dp[i][j] = dp[i-1][j-1];
                else if(pp[j-1] == '*'){
                    for(int k = 0; k <= i; k++){
                        dp[i][j] = dp[i-k][j-1];
                        if(dp[i][j]) break;
                    }
                }

            }
        }
        return dp[m][n];
    }
    //正则表达式匹配——https://leetcode.cn/problems/regular-expression-matching/
    public boolean isMatch2(String s, String p) {
        int m = s.length(), n = p.length();
        char[] ss = s.toCharArray();
        char[] pp = p.toCharArray();
        boolean[][] dp = new boolean[m+1][n+1];
        dp[0][0] = true;
        for(int j = 1; j < n; j+=2){
            if(pp[j] == '*') dp[0][j+1] = true;
            else break;
        }
        for(int i = 1; i <= m; i++){
            for(int j = 1; j <= n; j++){
                if(pp[j-1] == '*')
                    dp[i][j] = dp[i][j-2] || (pp[j-2] == ss[i-1] || pp[j-2] == '.') && dp[i-1][j];
                else dp[i][j] = (ss[i-1] == pp[j-1] || pp[j-1] == '.') && dp[i-1][j-1];
            }
        }
        return dp[m][n];
    }

}
